// https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247488241&idx=2&sn=374ca9d153bf4f0c44da7601013cb180&scene=21#wechat_redirect
// https://leetcode-cn.com/problems/binary-search/

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;

        if (target < nums[left] || target > nums[right])
            return -1;

        while (left <= right)
        {
            int middle = (left + right) / 2;

            if (nums[middle] > target)
                right = middle - 1;
            else if (nums[middle] < target)
                left = middle + 1;
            else
                return middle;
        }

        return -1;
    }
};

int main()
{
    Solution object = Solution();

    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 7;

    cout << object.search(nums, target) << endl;

    return 0;
}